package srcInterviewPrep;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;

public final class Boggle
{
    private static void GetBoggleWords(
        HashSet<String> wordsDict,
        char[][] m,
        int numRows,
        int numCols,
        int x,
        int y,
        String s,
        HashSet<String> detectedWords,
        HashSet<XYPair> used)
    {
        // argument validations

        XYPair xyPair = new XYPair(x,y);

        if (used.contains(xyPair))
        {
            return;
        }

        used.add(xyPair);

        String s1 = s + m[x][y];

        if (s1.length() >= 3
            && wordsDict.contains(s1)
            && !detectedWords.contains(s1))
        {
            detectedWords.add(s1);
        }

        List<XYPair> nbors = GetNeighbors(x, y, numRows, numCols);

        for (XYPair n : nbors)
        {
            GetBoggleWords(
                wordsDict,
                m,
                numRows,
                numCols,
                n.X,
                n.Y,
                s1,
                detectedWords,
                used);
        }

        used.remove(xyPair);
    }

    private static List<XYPair> GetNeighbors(int x, int y, int numRows, int numCols)
    {
        List<XYPair> nbors = new ArrayList<XYPair>();

        int xStart = Math.max(0, x-1);
        int yStart = Math.max(0, y-1);

        int xEnd = Math.min(x+1, numRows-1);
        int yEnd = Math.min(y+1, numCols-1);

        for (int i = xStart; i <= xEnd; ++i)
        {
            for (int j = yStart; j <= yEnd; ++j)
            {
                nbors.add(new XYPair(i,j));
            }
        }

        nbors.remove(new XYPair(x,y));

        return nbors;
    }

    public static HashSet<String> GetAllBoggleWords(
        HashSet<String> wordsDict,
        char[][] m,
        int numRows,
        int numCols)
    {
        HashSet<String> detectedWords = new HashSet<String>();

        for (int i = 0; i < numRows; ++i)
        {
            for (int j = 0; j < numCols; ++j)
            {
                HashSet<XYPair> used = new HashSet<XYPair>();

                GetBoggleWords(
                    wordsDict,
                    m,
                    numRows,
                    numCols,
                    i,
                    j,
                    "",
                    detectedWords,
                    used);
            }
        }

        return detectedWords;
    }
}
